package b_sorting_advance.b_quick_sort.questions;

import java.util.Arrays;

/**
 * 取数组中第n小的元素 (元素都不重复）
 * <p>
 * 一般思路： 排序一次后 获取 最快 NlogN
 * <p>
 * 快速排序的解法：
 * 从n个无序的顺序表中找出第k小的数，采用快排思想：
 * 先从n个元素中随便寻找一个数m作为分界点,m在列表中的位置为i
 * 当 i = k时，m就是我们要寻找的第k小的数；
 * 当 i > k时，我们就从1~i-1中查找；
 * 当 i < k时，就从i+1~n中查找。
 * <p>
 * 和快速排序不同， 每次我们只需要考虑半边
 * 随机时间复杂是 N + N/2 + N/4 .. + 1 = O(2N) 友谊是O(n)的复杂度
 *
 * ps:
 * 如果元素有重复的话, 还是使用三路快速排序的方法更有效
 */
public class FindNthRankNumberSolution {

    private static int partition(Comparable[] arr, int l, int r) {
        swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);
        Comparable v = arr[l];
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(v) < 0) {
                j++;
                swap(arr, j, i);
            }
        }
        swap(arr, l, j);
        return j;
    }

    private static void swap(Comparable[] arr, int m, int n) {
        Comparable temp = arr[m];
        arr[m] = arr[n];
        arr[n] = temp;
    }

    //求arr数组中[l...r]范围里第k小的数
    private static Comparable solve(Comparable[] originArr, int l, int r, int k) {
        Comparable[] arr = Arrays.copyOf(originArr, originArr.length);
        if (l == r) return arr[l];

        int p = partition(arr, l, r);

        if (k == p) {
            return arr[p]; // 当数组没有重复元素时, p正好就是排序的顺位
        } else if (k < p) {
            return solve(arr, l, p - 1, k);
        } else if (k > p) {
            return solve(arr, p + 1, r, k);
        }
        return null;
    }


    //这里k为0，即最小的数为第0小的数
    private static Comparable solve(Comparable[] arr, int k) {
        assert arr != null && k >= 0 && k < arr.length;
        return solve(arr, 0, arr.length - 1, k);
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 3, 5, 7, 6, 4, 2, 0};
        System.out.println(solve(arr, 0)); //  5
        System.out.println(solve(arr, 1)); // 32
        System.out.println(solve(arr, 2)); // 54
        System.out.println(solve(arr, 3)); // 54
    }
}
